%-------------------------------
%二次剩余习题
%-------------------------------
		\begin{Exercise}
			求模23的二次剩余和非二次剩余
		\end{Exercise}
		\jd{
			23的一个完全剩余系为{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23}，依次计算$i^2 (mod\ 23)$，计算结果组成的集合就是模23二次剩余组成的集合，完全剩余系中不包含在此集合中的元素就是非二次剩余。\par
			$
			1 ^2= 1 (mod 23),2 ^2= 4 (mod 23),3 ^2= 9 (mod 23),4 ^2= 16 (mod 23)\\
			5 ^2= 2 (mod 23),6 ^2= 13 (mod 23),7 ^2= 3 (mod 23),8 ^2= 18 (mod 23)\\
			9 ^2= 12 (mod 23),10 ^2= 8 (mod 23),11 ^2= 6 (mod 23),12 ^2= 6 (mod 23)\\
			13 ^2= 8 (mod 23),14 ^2= 12 (mod 23),15 ^2= 18 (mod 23),16 ^2= 3 (mod 23)\\
			17 ^2= 13 (mod 23),18 ^2= 2 (mod 23),19 ^2= 16 (mod 23),20 ^2= 9 (mod 23)\\
			21 ^2= 4 (mod 23),22 ^2= 1 (mod 23),23 ^2= 0 (mod 23)\\
			$
			二次剩余为0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\par
			非二次剩余5，7，10，11，14，15，17，19，20，21，22		
		}
		%sagemath函数求解二次剩余的过程，也可以直接使用quadratic_residues(23) 计算模23的所有二次剩余
		%		sage: for i in range(1,24):
		%		....:     print i,"^2=",mod(i^2,23),"(mod 23)"
		%		....:
		%		1 ^2= 1 (mod 23)
		%		2 ^2= 4 (mod 23)
		%		3 ^2= 9 (mod 23)
		%		4 ^2= 16 (mod 23)
		%		5 ^2= 2 (mod 23)
		%		6 ^2= 13 (mod 23)
		%		7 ^2= 3 (mod 23)
		%		8 ^2= 18 (mod 23)
		%		9 ^2= 12 (mod 23)
		%		10 ^2= 8 (mod 23)
		%		11 ^2= 6 (mod 23)
		%		12 ^2= 6 (mod 23)
		%		13 ^2= 8 (mod 23)
		%		14 ^2= 12 (mod 23)
		%		15 ^2= 18 (mod 23)
		%		16 ^2= 3 (mod 23)
		%		17 ^2= 13 (mod 23)
		%		18 ^2= 2 (mod 23)
		%		19 ^2= 16 (mod 23)
		%		20 ^2= 9 (mod 23)
		%		21 ^2= 4 (mod 23)
		%		22 ^2= 1 (mod 23)
		%		23 ^2= 0 (mod 23)
		%		sage:
		%		
		
		
		\begin{Exercise}
			求满足方程$E:y^2 \equiv x^2-2x+1 (mod\ 7)$的所有点。
		\end{Exercise}
		\jd{
			首先观察方程的左边是$y^2 (mod\ 7)$的形式，其最终结果是模7的二次剩余，我们计算模7的二次剩余，可知为：0，1，2，4。\par
			$1 ^2= 1 (mod 7),
			2 ^2= 4 (mod 7),
			3 ^2= 2 (mod 7),
			4 ^2= 2 (mod 7),
			5 ^2= 4 (mod 7),
			6 ^2= 1 (mod 7),
			7 ^2= 0 (mod 7)$\par
			$(7k)^2 \equiv 0(mod\ 7),(7k+1 or 6)^2 \equiv 1(mod\ 7),(7k+3 or 4)^2 \equiv 2(mod\ 7),(7k+2 or 5)^2 \equiv 4(mod\ 7)$
			以上方程等价于：\\
			\vspace{1cm} $x^2-2x+1 \equiv 0(mod\ 7)$\ or\ $x^2-2x+1 \equiv 1(mod\ 7)$\ or\ $x^2-2x+1 \equiv 2(mod\ 7)$\ or\ $x^2-2x+1 \equiv 4(mod\ 7)$,对这四个同余式进一步变形，得\par
			\vspace{1cm} $(x-1)^2 \equiv 0(mod\ 7)$\ or\ $(x-1)^2 \equiv 1(mod\ 7)$\ or\ $(x-1)^2 \equiv 2(mod\ 7)$\ or\ $(x-1)^2 \equiv 4(mod\ 7)$,根据模7的二次剩余，进一步知道：\par
			\vspace{1cm}$x \equiv 1(mod\ 7),x \equiv 9(mod\ 7),x \equiv 4(mod\ 7),x \equiv 6(mod\ 7)$\par
			所以满足以上方程的点为(0,1)(1,9)(6,9)(3,4)(4,4)(2,6)(5,6)只要对应的y和x于这些点同余就满足方程。
		}
		
		\begin{Exercise}
			利用欧拉判别条件判断2是否是29的二次剩余。
		\end{Exercise}
		\jd{
			29是奇素数，gcd(2,29)=1，根据欧拉判别条件$a^{\frac{p-1}{2}} = 2^{\frac{29-1}{2}} =2^14 =16384 \equiv -1(mod\ 29)$,所以2不是29的二次剩余。
		}
		
		\begin{Exercise}
			利用勒让德符号判断2是否是73的二次剩余。
		\end{Exercise}
		\jd{73为奇素数，根据书中定理我们有\par
			
			$
			(\frac{2}{73})= 
			\begin{cases}
			1,if\ p \equiv \pm 1(mod\ 8)\\
			-1,if\ p \equiv \pm 3(mod\ 8)\\
			\end{cases}
			$，
			
			
			$\because 73(mod\ 8)\equiv 1,\therefore (\frac{2}{73})=1 $,2是73的二次剩余。
		}
		
		\begin{Exercise}
			计算勒让德符号$(\frac{17}{37})$.
		\end{Exercise}
		
		\begin{Exercise}
			计算勒让德符号$(\frac{37}{25411})$(备注：25411为素数)
		\end{Exercise}
		\jd{
			$gcd(37,25411)=1$\\
			根据二次互反定律，我们有：\\
			$\left( \frac{37}{25411} \right) =(-1)^{\frac{37-1}{2} \frac{25411-1}{2}} (\frac{25411}{37})=(\frac{29}{37})=(-1)^{\frac{29-1}{2} \frac{37-1}{2}} (\frac{37}{29})=(\frac{8}{29})$,然后可以根据二次剩余的定义，知$(\frac{8}{29})=8^{\frac{29-1}{2}} (mod\ 29) \equiv 28 \equiv -1(mod\ 29)$
		}
